package Search;

import java.util.ArrayList;

import Main.Node;

public class AS2 extends GSearch {
	static ArrayList<Node> Q = new ArrayList<Node>();

	public static void search(Node initialState) {
		Q.add(initialState);
		calHeuristics(Q);
		int n = chooseNode(Q);
		while (!Q.isEmpty() && !Solved(Q.get(n))) {

			ArrayList<Node> x = expand(Q.remove(n));
			calHeuristics(x);
			while (!x.isEmpty()) {
				if (GSearch.checkDone(x.get(0).getBoard().getB())) {
					Q.add(0, x.get(0));
				}
				x.remove(0);
			}
			if (!Q.isEmpty()) {
				n = chooseNode(Q);
			}
		}
		if (!Q.isEmpty() && Solved(Q.get(n))) {
			displayPath(formPath(Q.get(n)));
			System.out.println("SOLUTION!!!");
		}
		if (Q.isEmpty()) {
			System.out.println("NO SOLUTION!!!");
		}
	}

	public static void calHeuristics(ArrayList<Node> x) {
		for (int i = 0; i < x.size(); i++) {
			if (!Solved(x.get(i))) {
				ArrayList<Node> temp = expand(x.get(i));
				nodesExpanded--;
				x.get(i).setHeuristics(temp.size());
			} else {
				x.get(i).setHeuristics(0);
			}
		}
	}

	public static int chooseNode(ArrayList<Node> q) {
		int max = 0;
		int maxv = q.get(0).getHeuristics() + q.get(0).getCostSoFar();
		for (int i = 1; i < q.size(); i++) {
			if (q.get(i).getHeuristics() + q.get(i).getCostSoFar() > maxv) {
				maxv = q.get(i).getHeuristics() + q.get(i).getCostSoFar();
				max = i;
			} else {
				if (q.get(i).getHeuristics() == 0) {
					return i;
				}
			}
		}
		return max;
	}

}
